package leecode.mid;

import org.junit.Test;

/**
 * @Author: xieZW
 * @Date: 2022/3/2 10:22
 * 输入：nums = [4,5,6,7,0,1,2], target = 0
 * 输出：4
 */
public class Index33 {

    @Test
    public void fun() {
        int[] a = {4, 5, 6, 7, 0, 1, 2};
        int search = search(a, 0);
        System.out.println("search = " + search);
    }

    public int search(int[] nums, int target) {

        // 判断 如果target小于最后一个数,在右半部分 ,如果target 大于第一个数,在左半部分;
        int length = nums.length;
        int lastNum = nums[length - 1];
        if (target <= lastNum) {
            int i = 0;
            //在右半部分
            return biSearch(i, nums, length, target);

        } else if (target >= lastNum) {
            int i = length;
            //在左半部分
            return biSearchLeft(i, nums, length, target);
        }
        return -1;
    }

    private int biSearchLeft(int i, int[] nums, int length, int target) {
        while (i > 0) {
            int index = (i + 0) / 2;
            if (nums[index] == target) {
                return index;
            } else if (nums[index] < target && nums[index] >= nums[0]) {
                return biSearch(i, nums, length, target);
            }
            i = (index + 0) / 2;
        }
        return -1;
    }

    private int biSearch(int i, int[] nums, int length, int target) {
        while (i < length - 1) {
            int index = (i + length) / 2;
            if (nums[index] == target) {
                return index;
            } else if (nums[index] > target && nums[index] <= nums[length - 1]) {
                return biSearchLeft(i, nums, length, target);
            }
            i = (index + length) / 2;
        }
        return -1;
    }
}
